Matematika Diskret: Anatomi Jaringan Transportasi

Jaringan transportasi adalah struktur matematis khusus yang digunakan untuk memodelkan pergerakan komoditas, data, atau bahan melalui sistem saluran terbatas. Ini mengubah graf berarah standar menjadi kerangka kerja fungsional dengan menentukan titik asal dan tujuan tertentu, sekaligus memberlakukan batasan fisik 'sumbatan' pada setiap koneksi dalam sistem.

Definisi Jaringan Transportasi

Menurut Definisi 10.1.1, jaringan transportasi (atau disebut saja jaringan) adalah graf berarah sederhana yang diberi bobot dan harus memenuhi tiga kriteria utama:

Properti (a): Sumber

Sebuah simpul yang ditentukan, yaitu sumber ($a$ atau $s$), mewakili titik asal. Ia tidak memiliki tepi masuk (derajat masuk = 0) dan berfungsi sebagai pemasok tak terbatas.

Properti (b): Tujuan

Sebuah simpul yang ditentukan, yaitu tujuan ($z$ atau $t$), mewakili konsumen akhir. Ia tidak memiliki tepi keluar (derajat keluar = 0).

Properti (c): Kapasitas

Bobot $C_{ij}$ dari setiap tepi berarah $(i, j)$ disebut kapasitas. Ini harus merupakan bilangan non-negatif ($C_{ij} \geq 0$), yang mewakili aliran maksimum yang dapat didukung oleh tepi tersebut.

Analog Dunia Nyata: Jaringan Listrik Regional

Untuk membuat konsep-konsep abstrak ini lebih hidup, pertimbangkan jaringan listrik regional:

Sumber: Pembangkit listrik tenaga air besar. Ia hanya menghasilkan energi; tidak ada listrik yang masuk ke bendungan dari jaringan itu sendiri.
Tujuan: Zona manufaktur industri berat. Ia mengonsumsi semua listrik yang masuk untuk menggerakkan mesinnya; tidak ada yang dikembalikan ke jaringan.
Tepi dan Kapasitas: Saluran transmisi adalah tepi. Kapasitasnya adalah arus maksimum yang dapat ditangani kabel fisik sebelum gagal karena panas.
Simpul Perantara: Stasiun penghubung lokal yang mengalihkan aliran tanpa 'mengonsumsi' (Konservasi Aliran).

Perbedaan Halus antara Kapasitas dan Aliran

Sangat penting untuk membedakan antara Kapasitas dan Aliran. Kapasitas $C_{ij}$ adalah sifat fisik statis—ia adalah volume potensial. Aliran $F_{ij}$ adalah volume aktual yang sedang bergerak pada saat tertentu. Pada slide ini, kita fokus secara eksklusif pada batasan arsitektural (kapasitas) daripada kondisi saat ini dari gerakan.

🎯 Prinsip Utama: Kendala Struktural

Setiap jaringan transportasi adalah graf berarah di mana aliran bergerak dari pemasok (Sumber) ke konsumen (Tujuan) melalui saluran yang dibatasi oleh kapasitas non-negatif.

Sumber: $deg^-(a) = 0 \quad | \quad$ Tujuan: $deg^+(z) = 0 \quad | \quad \text{Kapasitas}: C_{ij} \geq 0

PERTANYAAN 1

Apa tiga komponen wajib dari jaringan transportasi menurut Definisi 10.1.1?

Graf berarah, sumber/tujuan unik, dan kapasitas non-negatif.

Graf tak berarah, sumber tak terbatas, dan bobot negatif.

Graf berbobot, pencocokan bipartit, dan derajat masuk yang sama.

Graf sederhana, sumber dengan derajat masuk 1, dan tepi kapasitas nol.

PERTANYAAN 2

Apa perbedaan utama antara Kapasitas ($C_{ij}$) dan Aliran ($F_{ij}$)?

Kapasitas adalah batas maksimum; Aliran adalah jumlah aktual yang sedang bergerak saat ini.

Kapasitas bersifat dinamis; Aliran adalah sifat fisik statis.

Kapasitas hanya berlaku untuk tujuan; Aliran hanya berlaku untuk sumber.

Tidak ada perbedaan; mereka istilah yang dapat dipertukarkan dalam teori jaringan.

PERTANYAAN 3

Dalam konteks model jaringan listrik, apa yang mewakili Sumber?

Pembangkit listrik seperti pembangkit listrik tenaga air.

Wilayah permukiman yang mengonsumsi listrik.

Stasiun penghubung perantara yang mengalihkan daya.

Kabel tembaga fisik yang digunakan untuk transmisi.

PERTANYAAN 4

Nyatakan syarat agar simpul $z$ dianggap sebagai Tujuan.

Ia harus memiliki derajat keluar nol ($deg^+(z) = 0$).

Ia harus memiliki derajat masuk nol ($deg^-(z) = 0$).

Jumlah kapasitasnya harus tak terhingga.

Ia harus terhubung ke setiap simpul lain dalam graf.

PERTANYAAN 5

[🧩 SYSTEM_FORCED] Apa itu jaringan? (Fokus pada kriteria Definisi 10.1.1).

Graf berarah sederhana yang diberi bobot dengan sumber yang ditentukan (tidak ada tepi masuk), tujuan yang ditentukan (tidak ada tepi keluar), dan kapasitas non-negatif pada semua tepi.

Graf bipartit di mana setiap simpul memiliki tepi pencocokan.

Graf apa pun yang berisi lintasan dari simpul a ke simpul z.

Graf berarah di mana jumlah tepi sama dengan jumlah simpul.